﻿using System;
using System.Collections;
using System.Collections.Generic;

namespace Activity.V
{
	/// <summary>
	/// Бинарное сбалансированное дерево.
	/// </summary>
	public class AVLTree
	{
		#region Static

		/// <summary>
		/// Коэффициент балансировки узла.
		/// </summary>
		/// <returns>
		/// Возвращает: 0 если узел сбалансирован
		///				меньше 0 если высота левой ветви больше высоты правой ветви
		///				больше 0 если высота правой ветви больше высоты левой ветви
		/// </returns>
		public static int GetBalance(AVLNode node)
		{
			if (node == null) return 0;
			return AVLNode.GetHeightValue(node.Right) - AVLNode.GetHeightValue(node.Left);
		}

		/// <summary>
		/// Является ли узел сбалансированным.
		/// </summary>
		public static bool HasBalance(AVLNode node)
		{
			node.FixHeight();
			var balance = GetBalance(node);
			return balance < 2 && balance > -2;
		}

		/// <summary>
		/// Количество дочерних узлов относительно указанной вершины дерева включительно.
		/// </summary>
		/// <param name="node">Вершина относительно которой вести отсчет.</param>
		/// <returns>Количество узлов относительной заданной вершины дерева.</returns>
		public static int GetCount(AVLNode node)
		{
			var retVal = 0;
			// Используем прямой обход
			var iterator = PreOrder(node).GetEnumerator();
			// Обходим каждый элемент и считаем их количество
			while (iterator.MoveNext()) retVal++;
			return retVal;
		}

		/// <summary>
		/// Найти узел с наименьшим значением относительно указанного узла.
		/// </summary>
		/// <param name="node">Узел относительно которого вести поиск.</param>
		/// <returns>Возвращает самый левый узел который содержит наименьшее значение.</returns>
		public static AVLNode GetMin(AVLNode node)
		{
			if (node == null) return null;
			while (node.Left != null) node = node.Left;
			return node;
		}

		/// <summary>
		/// Найти узел с наибольшим значением относительно указанного узла.
		/// </summary>
		/// <param name="node">Узел относительно которого вести поиск.</param>
		/// <returns>Возвращает самый правый узел который содержит наибольшее значение.</returns>
		public static AVLNode GetMax(AVLNode node)
		{
			if (node == null) return null;
			while (node.Left != null) node = node.Left;
			return node;
		}

		/// <summary>
		/// Повернуть ветку вправо.
		/// </summary>
		/// <param name="node">Экземпляр узла.</param>
		/// <returns>Возвращает узел который используется в качестве нового корня.</returns>
		public static AVLNode RotateRight(AVLNode node)
		{
			// Левый узел является новым корнем
			var retVal = node.Left;
			retVal.Parent = node.Parent;

			// Корень.Левый = Левый.Правый
			node.Left = retVal.Right;
			if (node.Left != null) node.Left.Parent = node;

			// Левый.Правый = Корень
			retVal.Right = node;
			if (retVal.Right != null) retVal.Right.Parent = retVal;

			// Обновляем высоту
			node.FixHeight();
			retVal.FixHeight();

			return retVal;
		}

		/// <summary>
		/// Повернуть ветку влево.
		/// </summary>
		/// <param name="node">Экземпляр узла.</param>
		/// <returns>Возвращает узел который используется в качестве нового корня.</returns>
		public static AVLNode RotateLeft(AVLNode node)
		{
			// Правый узел является новым корнем
			var retVal = node.Right;
			retVal.Parent = node.Parent;

			// Корень.Правый = Правый.Левый
			node.Right = retVal.Left;
			if (node.Right != null) node.Right.Parent = node;

			// Правый.Левый = Корень
			retVal.Left = node;
			if (retVal.Left != null) retVal.Left.Parent = retVal;

			// Обновляем высоту
			node.FixHeight();
			retVal.FixHeight();

			return retVal;
		}

		/// <summary>
		/// Прямой (префиксный) обход дерева относительно указанного узла.
		/// Очередность: вершина -> левое поддерево -> правое поддерево.
		/// </summary>
		/// <param name="node">Узел относительно которого начать обход.</param>
		/// <returns>Элементы дерева в указанной очередности.</returns>
		public static IEnumerable<AVLNode> PreOrder(AVLNode node)
		{
			var stack = new Stack<AVLNode>();
			while (stack.Count > 0 || node != null)
			{
				if (node != null)
				{
					yield return node;
					stack.Push(node);
					node = node.Left;
				}
				else
				{
					node = stack.Pop();
					node = node.Right;
				}
			}
		}

		/// <summary>
		/// Вывести на экран полный путь до указанного узла.
		/// </summary>
		/// <param name="node">Узел до которого необходимы показать путь</param>
		public static void PrintPath(AVLNode node)
		{
			var stack = new Stack<AVLNode>();
			// Собираем путь до вершины дерева
			while (node != null)
			{
				stack.Push(node);
				node = node.Parent;
			}
			var level = 0;
			var prefix = string.Empty;
			// Отображаем вершину
			PrintNode(stack.Pop(), prefix, level++, ConsoleColor.Cyan);
			// Отображаем путь
			while (stack.Count > 1)
			{
				prefix += "  ";
				PrintNode(stack.Pop(), prefix, level++, ConsoleColor.White);
			}
			// Отображаем заданный узел
			if (stack.Count > 0) PrintNode(stack.Pop(), prefix, level, ConsoleColor.Green);
		}

		/// <summary>
		/// Вывести на экран полное дерево относительно заданной вершины.
		/// </summary>
		/// <param name="node">Вершина дерева.</param>
		public static void PrintTree(AVLNode node)
		{
			if (node == null) Console.WriteLine("<null>");
			else PrintTree(node, string.Empty, AVLNode.GetDepth(node), ConsoleColor.Cyan);
		}

		/// <summary>
		/// Вывести на экран полное дерево относительно заданной вершины.
		/// </summary>
		/// <param name="node">Вершина дерева.</param>
		/// <param name="prefix">Предшествующий текст [префикс].</param>
		/// <param name="level">Глубина узла относительно корня.</param>
		/// <param name="color">Цвет текста.</param>
		private static void PrintTree(AVLNode node, string prefix, int level, ConsoleColor color)
		{
			if (node == null) return;
			PrintNode(node, prefix, level, color);
			PrintTree(node.Left, prefix + (level == 0 ? "| " : "| "), level + 1, ConsoleColor.Red);
			PrintTree(node.Right, prefix + "| ", level + 1, ConsoleColor.Green);
		}

		/// <summary>
		/// Вывести на экран значение узла.
		/// </summary>
		/// <param name="node">Экземпляр узла.</param>
		/// <param name="prefix">Предшествующий текст [префикс].</param>
		/// <param name="level">Глубина узла относительно корня.</param>
		/// <param name="color">Цвет текста.</param>
		private static void PrintNode(AVLNode node, string prefix, int level, ConsoleColor color)
		{
			if (node == null) return;
			var consoleColor = Console.ForegroundColor;
			var value = node.Value.ToString();
			Console.Write(prefix);
			Console.Write("+");
			Console.ForegroundColor = color;
			Console.Write("[{0}]", value);
			Console.ForegroundColor = consoleColor;
			Console.WriteLine(" (D:{0} H:{1} B:{2})", level, node.Height, GetBalance(node));
		}

		#endregion

		protected IComparer comparer;
		protected AVLNode root;

		/// <summary>
		/// Создать новый экземпляр бинарного дерева.
		/// </summary>
		public AVLTree()
		{
			// Используем объектов сравнение по умолчанию
			comparer = Comparer<object>.Default;
		}

		/// <summary>
		/// Создать новый экземпляр бинарного дерева.
		/// </summary>
		/// <param name="comparer">Объект который содержит метод для сравнения значений узлов.</param>
		public AVLTree(IComparer comparer)
		{
			this.comparer = comparer;
		}

		/// <summary>
		/// Общее количество узлов в дереве.
		/// </summary>
		public int Count { get { return root != null ? GetCount(root) : 0; } }

		/// <summary>
		/// Является ли дерево сбалансированным.
		/// </summary>
		public bool HasBalance()
		{
			// http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
			return GetHeight() <= GetMaxHeight();
		}

		/// <summary>
		/// Полная высота дерева.
		/// </summary>
		public int GetHeight()
		{
			return AVLNode.GetMaxHeight(root);
		}

		/// <summary>
		/// Максимальная высота сбалансированного дерева для текущего количества элементов.
		/// </summary>
		public int GetMaxHeight()
		{
			// +1 после округления вниз
			// +1 поскольку возможно различие на единицу высоты
			return (int)Math.Floor(Math.Log(Count, 2)) + 1 + 1;
		}

		/// <summary>
		/// Вывести на экран дерево.
		/// </summary>
		public void Print()
		{
			PrintTree(root);
		}

		/// <summary>
		/// Очистить дерево.
		/// </summary>
		public void Clear()
		{
			root = null;
		}

		/// <summary>
		/// Найти узел с указанным значением.
		/// </summary>
		/// <param name="value">Значение для поиска.</param>
		/// <returns>Возвращает узел с указанным значением если найден; в противном случае null.</returns>
		public AVLNode Find(object value)
		{
			return Find(root, value);
		}

		/// <summary>
		/// Найти узел с указанным значением относительно заданного узла.
		/// </summary>
		/// <param name="node">Узел относительно которого вести поиск.</param>
		/// <param name="value">Значение для поиска.</param>
		/// <returns>Возвращает узел с указанным значением если найден; в противном случае null.</returns>
		public AVLNode Find(AVLNode node, object value)
		{
			// Ищем до тех пор пока имеется правый или левый узел
			while (node != null)
			{
				// Сравниваем значения
				var i = Compare(value, node.Value);
				// Идем в левый узел если заданное значение меньше чем значение узла
				if (i < 0) node = node.Left;
				// Идем в правый узел если заданное значение больше чем значение узла
				else if (i > 0) node = node.Right;
				// Выходим из цикла когда заданное значение совпадает со значением узла
				else break;
			}
			return node;
		}

		/// <summary>
		/// Добавить новое значение в дерево.
		/// </summary>
		/// <param name="value">Значение которое добавить.</param>
		/// <returns>Новый узел который содержит указанное значение.</returns>
		public AVLNode Add(object value)
		{
			int i;
			AVLNode parent = null;
			var current = root;
			// Ищем пустой узел
			while (current != null)
			{
				parent = current;
				i = Compare(value, current.Value);
				// Если заданное значение меньше значение узла, то следуем по левой ветке
				if (i < 0) current = current.Left;
				// В противном случае следуем по правой ветке
				else current = current.Right;
			}

			// Создаем новый узел
			var retVal = new AVLNode { Value = value };
			// Если пустой узел не найден, значит дерево не имеет корня
			if (parent == null) root = retVal;
			else
			{
				// Выставить родительский узел
				retVal.Parent = parent;
				// Сравниваем значения узлов
				i = Compare(value, parent.Value);
				// Если заданное значение меньше значение родительского узла, то узел записывается в левую сторону
				if (i < 0) parent.Left = retVal;
				// В противном случае узел записывается в правую сторону
				else parent.Right = retVal;
			}

			// Балансировка дерева после добавления
			BalanceTree(parent);
			return retVal;
		}

		/// <summary>
		/// Удалить указанное значение из дерева.
		/// </summary>
		/// <param name="value">Значение которое необходимо удалить</param>
		/// <returns>Возвращает истину если заданное значение найдено и удалено; в противном случае ложь.</returns>
		public bool Remove(object value)
		{
			return Remove(Find(value));
		}

		/// <summary>
		/// Удалить указанный узел из дерева.
		/// </summary>
		/// <param name="node">Узел который необходимо удалить.</param>
		/// <returns>Возвращает ложь если заданный узел не указан; в противном случае истину.</returns>
		public bool Remove(AVLNode node)
		{
			// Нечего удалять
			if (node == null) return false;

			// Если узел содержит несколько веток
			if (node.Left != null && node.Right != null)
			{
				// Ищем узел с минимальным значением относительно его правой ветки
				// У этого узла как правило нету дочерних веток, поэтому его можно спокойно удалять
				var min = GetMin(node.Right);
				// Копируем найденное значение в узел
				node.Value = min.Value;
				// Удаляем найденный свободный узел
				Remove(min);
			}
			// В противном случаем узел содержит либо одну ветку, либо вообще не имеет веток
			else
			{
				var parent = node.Parent;
				var any = node.Left ?? node.Right;
				// Если он является левой веткой, то в левую ветку родителя записываем его любую активную ветку
				if (node.IsLeft) parent.Left = any;
				// Если он является правой веткой, то в правую ветку родителя записываем его любую активную ветку
				else if (node.IsRight) parent.Right = any;
				// Отвязать от родителя
				node.Parent = null;
			}
			return true;
		}

		/// <summary>
		/// Балансировать все дерево начиная с указанного узла до вершины.
		/// </summary>
		/// <param name="node">Узел с которого начать балансировку.</param>
		public void BalanceTree(AVLNode node)
		{
			while (node != null)
			{
				node.Right = BalanceNode(node.Right);
				node.Left = BalanceNode(node.Left);
				node = node.Parent;
			}

			// Балансировка корня
			BalanceNode(root);
		}

		/// <summary>
		/// Балансировка указанного узла.
		/// </summary>
		/// <param name="node">экземпляр узла.</param>
		private AVLNode BalanceNode(AVLNode node)
		{
			// Ссылки:
			// http://upload.wikimedia.org/wikipedia/commons/c/c4/Tree_Rebalancing.gif
			// http://upload.wikimedia.org/wikipedia/commons/f/f5/AVL_Tree_Rebalancing.svg

			// Нечего балансировать
			if (node == null) return null;
			// Пересчитать высоту узла
			node.FixHeight();

			var retVal = node;
			var factor = GetBalance(node);
			if (factor > 1) // Правая ветвь тяжелее [Right Case]
			{
				// Правое вращение для перехода: Right-Left -> Right-Right
				if (GetBalance(node.Right) < 0) // [Right-Left Case]
					node.Right = RotateRight(node.Right);
				// Левое вращение [Right-Right Case]
				retVal = RotateLeft(node);
			}
			else if (factor < -1) // Левая ветвь тяжелее [Left Case]
			{
				// Левое вращение для перехода: Left-Right -> Left-Left
				if (GetBalance(node.Left) > 0) // [Left-Right Case]
					node.Left = RotateLeft(node.Left);
				// Правое вращение [Left-Left Case]
				retVal = RotateRight(node);
			}
			else return retVal; // Ветви сбалансированы

			// Обновляем ссылку в родителе
			if (node == root) root = retVal;
			else if (node.IsRight) node.Parent.Right = node;
			else if (node.IsLeft) node.Parent.Left = node;

			return retVal;
		}

		/// <summary>
		/// Сравнить объекты используя встроенный компаратор.
		/// </summary>
		/// <param name="x">ОбЪект для сравнения.</param>
		/// <param name="y">ОбЪект для сравнения.</param>
		/// <returns>
		/// Возвращает:	меньше нуля когда	х меньше y; 
		///				ноль когда			х равен y; 
		///				больше нуля когда	х больше y;
		/// </returns>
		protected int Compare(object x, object y)
		{
			return comparer.Compare(x, y);
		}
	}
}
